/***尚硅谷Java数据结构与java算法                   ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***希尔排序     移位式希尔排序       P63          ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
//用于获取系统时间
#include <ctime>
//用于生成随机数
#include <cstdlib>
using std::cout;
using std::endl;
#define MAX 500000

void printArr(int *arr, int size)
{
    for(int i=0;i<size;i++)
    {
        std::cout<<arr[i]<<"\t";
    }
    std::cout<<std::endl;
}

void quickSort(int *arr, int size)
{
    int temp=0;
    int inter=size/2;
    //每轮递增因子  
    //第一层循环时间复杂度   O(log2 N)
    for(;inter>0;inter/=2){
        //对每一个分组使用插入排序
        //比如inter=2；   i=iner, j=inter-inter=0,  
        //时间复杂度 O(N)
        for(int i=inter;i<size;i++){
            //比较分组的  前两个  前三个  前四个  是插入排序
            //时间复杂度  O()
            temp=arr[i];
            int j=i-inter;
            for (; j>=0; j-=inter)
            {
                if(temp<arr[j]){
                    arr[j+inter]=arr[j];
                }
                else 
                    break;
            }  
            arr[j+inter]=temp;
        }
        
    }
}

int main(int argc, char **argv)
{
    //使用系统时间生成一个随机数种子
    srand(time(NULL));    
    int *array=new int[MAX];
    for(int i=0;i<MAX;i++){
        array[i]=rand()%MAX;
        //cout<<array[i]<<endl;
    }
    //printArr(array,MAX);
    time_t now=time(NULL);
    std::cout<<"now="<<now<<std::endl;
    quickSort(array,MAX);
    //printArr(array,MAX);
    time_t newNow=time(NULL);
    std::cout<<"newNow="<<newNow<<std::endl;
    std::cout<<"一共花了"<<newNow-now<<"秒"<<endl;
    delete[] array;
    return 0;
}